package com.leetcode.algorithm.y22.m07;

import java.util.Arrays;

/**
 * 567. 字符串的排列
 * 
 * https://leetcode.cn/problems/permutation-in-string/
 * 
 * @author jie.deng
 *
 */
public class Question0567Solution01 {

	public boolean checkInclusion(String s1, String s2) {
		// s1字符串中各字母个数
		int[] cntArr = new int[26];
		for (int i = 0; i < s1.length(); i++) {
			cntArr[s1.charAt(i) - 'a']++;
		}
		int winSize = s1.length();

		for (int beginIdx = 0; beginIdx + winSize - 1 < s2.length(); beginIdx++) {
			boolean flag = checkInclusion(Arrays.copyOf(cntArr, cntArr.length),
					s2.substring(beginIdx, beginIdx + winSize));
			if (flag) {
				return true;
			}
		}

		return false;
	}

	private boolean checkInclusion(int[] cntArr, String s) {
		for (int i = 0; i < s.length(); i++) {
			int idx = s.charAt(i) - 'a';
			if (cntArr[idx] == 0) {
				return false;
			}
			cntArr[idx]--;
		}
		return true;
	}

}
